计数排序 1

比较排序

Quicksort usually has a running time of , but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat n×log(n)(worst-case) running time, since represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).
快速排序运行时间为n×log(n),有没有再快一点的排序算法呢？通常来说是不可能的。大多数的排序算法属于比较型排序，意即，通过元素间两两比较来实现一组数的排序。比较排序的运行时间（最坏情况）无法比n×log(n)更快，因为 n×log(n) 是确定一组数中每个数最终排序位置的最小比较次数。具体细节可以参看这些笔记

其他排序

However, for certain types of input, it is more efficient to use a non-comparison sorting algorithm. This will make it possible to sort lists even in linear time. These challenges will cover Counting Sort, a fast way to sort lists where the elements have a small number of possible values, such as integers within a certain range. We will start with an easy task - counting.
但是，对于某些特定输入，使用非比较的排序算法可能更为有效。这有可能实现线性时间内的排序。接下来的任务将涉及计数排序，一种当所有元素的取值都比较小，如处于一个较小的数据范围内的整数时的快速的排序方法。我们先来完成一个简单的任务：计数。

任务

Given a list of integers, can you count and output the number of times each value appears?

Hint: There is no need to sort the data, you just need to count it.
给你一组整数，你能统计并输出每个数出现的次数吗？
提示：没必要对数据排序，你仅需要做统计

输入格式

There will be two lines of input:

  • the size of the list
  • space-separated numbers that make up the list
    Output Format
    Output the number of times every number from to (inclusive) appears on the list.
    输入有两行：
    -这组数的个数n
    -以空格隔开的这组数

    约束

    100<=n<=10^6
    0<=x<100 (x为整数)

输入样例

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33

输出样例

0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2

解释

The output states that 0 appears 0 times, 1 appears 2 times, 2 appears 0 times, and so on in the given input array.
输出显示0出现0次，1出现2次，2出现0次，…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int a[100];
int main() {
    int n,val;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>val;
        a[val]++;
    }
    for(int i=0;i<100;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}